package com.squirrel.michale;

import java.util.ArrayList;
import java.util.List;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/1 12:12 PM
 * @company Michale Squirrel
 * @link
 * @description 2467. 树上最大得分和路径
 * 中等
 * 15
 * 相关企业
 * 一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 在树中有一条边。
 * <p>
 * 在每一个节点 i 处有一扇门。同时给你一个都是偶数的数组 amount ，其中 amount[i] 表示：
 * <p>
 * 如果 amount[i] 的值是负数，那么它表示打开节点 i 处门扣除的分数。
 * 如果 amount[i] 的值是正数，那么它表示打开节点 i 处门加上的分数。
 * 游戏按照如下规则进行：
 * <p>
 * 一开始，Alice 在节点 0 处，Bob 在节点 bob 处。
 * 每一秒钟，Alice 和 Bob 分别 移动到相邻的节点。Alice 朝着某个 叶子结点 移动，Bob 朝着节点 0 移动。
 * 对于他们之间路径上的 每一个 节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：
 * 如果门 已经打开 （被另一个人打开），不会有额外加分也不会扣分。
 * 如果 Alice 和 Bob 同时 到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣 c 分，那么 Alice 和 Bob 分别扣 c / 2 分。如果这扇门的加分为 c ，那么他们分别加 c / 2 分。
 * 如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果 Bob 到达了节点 0 ，他也会停止移动。注意这些事件互相 独立 ，不会影响另一方移动。
 * 请你返回 Alice 朝最优叶子结点移动的 最大 净得分。
 */
public class LeetCode2467 {

    // Reference:https://www.bilibili.com/video/BV1qe4y1G7jy/?spm_id_from=333.337.search-card.all.click

    int bob;
    int result = Integer.MIN_VALUE / 2;
    int[] amount;
    int[] bobTime;
    List<Integer>[] tree;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {

        int n = amount.length;
        this.bob = bob;
        this.amount = amount;
        this.bobTime = new int[n];
        this.tree = new List[n];
        for (int i = 0; i < n; i++) {
            bobTime[i] = Integer.MAX_VALUE / 2;
        }

        for (int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            tree[x].add(y);
            tree[y].add(x);
        }
        dfsBob(0, -1, 0);
        dfsAlice(0, -1, 0, 0);
        return result;
    }


    public void dfsBob(int cur, int parent, int step) {
        if (cur == bob) {
            bobTime[cur] = 0;
            return;
        }

        int toBob = Integer.MAX_VALUE / 2;
        for (int next : tree[cur]) {
            if (next != parent) {
                dfsBob(next, cur, step + 1);
            }
            toBob = Math.min(toBob, bobTime[next] + 1);
        }
        bobTime[cur] = toBob;
    }

    void dfsAlice(int cur, int parent, int step, int score) {
        if (step == bobTime[cur]) {
            score += amount[cur] / 2;
        } else if (step < bobTime[cur]) {
            score += amount[cur];
        }

        if (tree[cur].size() == 1 && tree[cur].get(0) == parent) {
            result = Math.max(result, score);
            return;
        }
        for (int next : tree[cur]) {
            if (next != parent) {
                dfsAlice(next, cur, step + 1, score);
            }
        }
    }


    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {1, 2}, {1, 3}, {3, 4}};

        int bob = 3;
        int[] amount = new int[]{-2, 4, 2, -4, 6};

        LeetCode2467 leetCode2467 = new LeetCode2467();
        // 预期结果 6
        System.out.println(leetCode2467.mostProfitablePath(edges, bob, amount));
    }

}
